


	Rezolvarea prin backtracking sau orice alta metoda de generare
exhaustiva si testare a tuturor configuratiilor posibile cade de la bun
inceput. Sunt 2 motive de descurajare: a) spatiul de explorat este imens;
b) parametrii problemei sunt dependenti functional unul de celalalt.

	Conform restrictiilor (2),(3), cele N acadele produse zilnic si ambalate
cate L in B cutii sunt invelite in N invelisuri diferite, corespunzatoare celor
N tiputi disponibile. -> L*B = N.

	De asemenea, sa reformulam restrictia 4 astfel: pt. fiecare tip de ambalaj
din cele N, fie el x, si pt. orice alt tip y de ambalaj din cele N-1 ramase dis-
ponibile, exista o singura cutie cu x si y, produsa in cele D zile ale ciclului
de profuctie. Dar, intr-o cutie, x este alaturi de L-1 invelisuri diferite, iar
x nu poate sa apara in mai multe cutii produse in aceeasi zi. Rezulta ca la
capatul celor D zile, fiind zilnic alaturi de L-1 invelisuri diferite,x trebuie
sa acopere N-1 posibilitati de asociere. Pt. ca parametrii sunt constanti, obtinem
ecuatia: D*(L-1) = N-1. La cele 2 ecuatii se adauga inegalitatea B>1.

	B*L = N		(c1)
 	D*(L-1) = N-1	(c2)
	B>1		(c3)

Teorema:	Fie Lv o valoare alui L, a.i. Lv satisface conditiile (c1),(c2) si
-------	 incecuatia (c3). Atunci Lv satisface restrictiile (1)-(4) ale problemei.

-> Algoritm de rezolvare:
-------------------------

min = infinit

pentru fiecare L din [2,N-1] executa

	daca N este divizibil prin L si N-1 este divizibil prin L-1 atunci
	{
	B = N/L
	D=(N-1)/(L-1)
	daca |D-B|<min atunci {Lmin=L ; Bmin=B ; Dmin=D ; min = |D-B| }	
	}

daca min<>infinit atunci rezultate Lmin,bmin,Dmin
		  altfel rezultate "No solution"


	Algoritmul functioneaza acceptabil pt. valori medii ale lui N. Dar, descrierea
datelor problemei precizeaza ca valoarea lui N poate fi un intreg lung. Intr-adevar,
datele de test din concurs contin valori mari ale lui N. Pt. o astfel de valoare,
fie N=2*10^9, algoritmul devine lent. De exemplu, in cazul unui calculator la 300 MHz,
sa presupunem ca sunt necesare 100 de cicluri de masina (aprox. 3.34*10^(-7) sec.)
pt. prelucrarea fiecarei valori posibile ale lui L. Atunci timpul necesar rezolvarii
este aprox. 672 sec. (>11 minute).